package com.umgsai.wx.backend.test;

import com.google.common.collect.Lists;

import java.util.List;

public class WordBreak {

    public static void main(String[] args) {
//        String s = "applepenapple";
//        List<String> wordDict = Lists.newArrayList("apple", "pen");
//        String s = "catsandog";
//        List<String> wordDict = Lists.newArrayList("cats", "dog", "sand", "and", "cat");

        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        List<String> wordDict = Lists.newArrayList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa");
        boolean b = wordBreak(s, wordDict);
        System.out.println(b);
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        List<String> startList = Lists.newArrayList();
        for (String s1 : wordDict) {
            if (s1.equals(s)) {
                return true;
            }
            if (s.startsWith(s1)) {
//                return wordBreak(s.substring(s1.length()), wordDict);
                startList.add(s1);
            }
        }
        for (String s1 : startList) {
            if (wordBreak(s.substring(s1.length()), wordDict)) {
                return true;
            }
        }
        return false;
    }
}
